#define _CRT_SECURE_NO_WARNINGS 1
class Trie {
public:
    struct TireNode
    {
        char value;
        vector<TireNode*> childs;
        bool isEnd = false;
        TireNode()
            :childs(26, nullptr)
        {}
    };

    Trie()
    {
        head = new TireNode();
    }

    void insert(string word)
    {
        TireNode* cur = head;
        for (auto& ch : word)
        {
            if (cur->childs[ch - 'a'] == nullptr)
            {
                TireNode* newNode = new TireNode;
                newNode->value = ch;
                cur->childs[ch - 'a'] = newNode;
            }
            cur = cur->childs[ch - 'a'];
        }
        cur->isEnd = true;
    }

    bool search(string word)
    {
        TireNode* cur = head;
        for (auto& ch : word)
        {
            if (cur->childs[ch - 'a'] == nullptr)
            {
                return false;
            }
            else
            {
                cur = cur->childs[ch - 'a'];
            }
        }
        return cur->isEnd == true;
    }

    bool startsWith(string prefix)
    {
        TireNode* cur = head;
        for (auto& ch : prefix)
        {
            if (cur->childs[ch - 'a'] == nullptr)
            {
                return false;
            }
            else
            {
                cur = cur->childs[ch - 'a'];
            }
        }
        return true;
    }
private:
    TireNode* head;
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */